題目描述

給定兩個排好順序的vector
請輸出他們的中間數
並將計算時間卡在O(log(兩者長度和))

思維

寫一個新的vector，把兩個vector排進去再sort他，接著就按位置取中間數就行。

程式碼

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int> nums3;
        double ans;
        nums3.insert(nums3.end(),nums1.begin(),nums1.end());
        nums3.insert(nums3.end(),nums2.begin(),nums2.end());
        sort(nums3.begin(),nums3.end());
        if(nums3.size()%2==1)
            ans=nums3[((nums3.size())-1)/2];
        else
        {
            ans=(nums3[(nums3.size())/2]+nums3[(nums3.size())/2-1])/2.0;
        }
        return ans;
    }
};

心路歷程

這題在Leetcode裡面屬於Hard的題目，所以原先我其實有點想要跳過.....
但還是按進去看了一下，發現其實並不是沒有想法，所以還是寫了。
原本看到O(log(n))還真的想說是不是要用二元法來跑，但可能腦袋一抽......
我就突然寫成這個版本，而且還覺得簡單易懂，而且這個方法雖然我是不知道多快啦，但是過了哈哈哈！
不過話說....自從我認識sort....我好像就沒在自己寫sort了→懶散的廢物